package club.vann.nowcoder;

import club.vann.nowcoder.common.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>难度：Medium</p>
 * <p>题目：判断一棵树是否是搜索二叉树</p>
 * <p>描述：给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。
 * 示例1
 * 输入
 * 复制
 * {2,1,3}
 * 返回值
 * 复制
 * [true,true]
 * 备注:
 * n \leq 500000n≤500000</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-19:17:15:36
 */
public class NC60 {
    public static void main(String[] args) {
        NC60 nc60 = new NC60();
        System.out.println("Result["+Arrays.toString(TestCase.ANS)+"] : " + Arrays.toString(nc60.judgeIt(TestCase.ROOT)));
        System.out.println("Result["+Arrays.toString(TestCase.ANS1)+"] : " + Arrays.toString(nc60.judgeIt(TestCase.ROOT1)));
    }

    /**
     *
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean[] ans = new boolean[2];
        ans[0] = isSearchTreeNode(root);
        ans[1] = isAllTreeNode(root);
        return ans;
    }

    /**
     * 判断一棵树是否是搜索二叉树。
     * @param root
     * @return
     */
    private boolean isSearchTreeNode(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.left != null && root.left.val > root.val) {
            return false;
        }

        if(root.right != null && root.right.val < root.val) {
            return false;
        }
        return isSearchTreeNode(root.left) && isSearchTreeNode(root.right);
    }

    /**
     * 判断一个树是否是完全二叉树。
     *
     * @param root
     * @return
     */
    private boolean isAllTreeNode(TreeNode root) {
        if(root == null) {
            return true;
        }
        List<ANode> list = new ArrayList<>();
        list.add(new ANode(root, 1));
        int i = 0;
        while(i < list.size()) {
            ANode aNode = list.get(i);
            TreeNode node = aNode.node;
            int code = aNode.code;
            if(node != null) {
                list.add(new ANode(node.left, code*2));
                list.add(new ANode(node.right, code*2+1));
            }
            i ++;
        }
        return list.get(i-1).code == list.size();
    }

    class ANode {
        TreeNode node;
        int code;
        ANode(TreeNode node, int code) {
            this.node = node;
            this.code = code;
        }
    }

    static class TestCase {
        public static boolean[] ANS = {true,true};
        public static TreeNode ROOT = TreeNode.deserialize("[2,1,3]");

        public static boolean[] ANS1 = {true,false};
        public static TreeNode ROOT1 = TreeNode.deserialize("[2,1,3,#,#,#,4]");
    }
}
